---
title: "带分数"
created: 2025-11-28
tags:
  - 算法
---

# 带分数

## 题目 [带分数](https://www.acwing.com/problem/content/1211/)

![[image-ebd005f3.png]]

## 思路分析

![[image-44f53cf2.png]]

问题逐渐简化 变成了先求1~9的全排列 再把每一个排列想办法分成abc三个部分 若abc三部分加起来能等于输入的数 就成立

另外需要注意除法丢失精度问题 变成乘法

![[image-206a4c7b.png]]

求全排列 就可以用前面得到的两种方法了 dfs或者next\_permutation

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=10;

int path[N];

bool st[N];

int x,res;

int calc(int l,int r){

    int ans=0;

    for(int i=l;i<=r;i++)

        ans=ans*10+path[i];

    return ans;

}

void dfs(int u){

    if(u==10){

        for(int i=1;i<=7;i++){

            for(int j=i+1;j<=8;j++){

                int a=calc(1,i);

                int b=calc(i+1,j);

                int c=calc(j+1,9);

                if(a*c+b==c*x)

                    res++;

            }

        }

        return;

    }

    for(int i=1;i<=9;i++){

        if(!st[i]){

            st[i]=true;

            path[u]=i;

            dfs(u+1);

            path[u]=0;

            st[i]=false;

        }

    }

}

int main()

{

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    cin>>x;

    dfs(1);

    cout<<res;

    return 0;

}
```

```cpp
#include<bits/stdc++.h>

using namespace std;

vector<int> alls={1,2,3,4,5,6,7,8,9};

int x,res;

int calc(int l,int r){

    int ans=0;

    for(int i=l;i<=r;i++)

        ans=ans*10+alls[i];

    return ans;

}

int main()

{

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    cin>>x;

    do{

        for(int i=0;i<=6;i++){

            for(int j=i+1;j<=7;j++){

                int a=calc(0,i);

                int b=calc(i+1,j);

                int c=calc(j+1,8);

                if(a*c+b==c*x)

                    res++;

            }

        }

    }while(next_permutation(alls.begin(),alls.end()));

    cout<<res;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[全排列（考虑顺序）|全排列（考虑顺序）]] 🏠 [[00-刷题理模型]] ➡️ [[排列数字|排列数字]]